/* octuplets-copy-variables.c */

/** based on a true story... **/

#include <stdio.h>
#include <stdlib.h>
#include <sys/wait.h>
#include <unistd.h>
#include <errno.h>
#include <time.h>
#include <stdbool.h>
#include <string.h>

#define MAX_NEXT_POSITON_SIZE 8

typedef struct _position {
	int x;
	int y;
}postion_c;

typedef struct _board_element {
	int depth;
	int step;
}board_element;

int m;
int n;
board_element** p_board;
postion_c p_start;
postion_c p_prev;
int cur_step;
int cur_depth;
bool is_root;
char ch_pipe;

postion_c next_pos[MAX_NEXT_POSITON_SIZE];
int cur_choice_index;

int pipe_parent_write;
int pipe_child[2];
int choice_size;

void alloc_board(int m, int n) {
	if (p_board == NULL) {
		if (m <= 0 || n <= 0) {
			printf("Invalid argument(s)\n");
			printf("USAGE: a.out <m> <n>\n");
		}
		p_board = (board_element**)calloc(m, sizeof(board_element*));
		for (int i = 0; i < m; ++i) {
			*(p_board + i) = (board_element*)calloc(n, sizeof(board_element));
		}
	}
}

bool is_pos_not_duplication(postion_c pos) {
	bool b_ret = false;
	if (pos.x >= m || pos.y >= n || p_board == NULL) {
		return b_ret;
	}
	if (p_board[pos.x][pos.y].step == 0) {
		b_ret = true;
	}
	return b_ret;
}
//get next position, valid positive; invalid negative
int get_pos(postion_c sp) {
	int i_ret;
	memset(next_pos, 0, sizeof(next_pos));
	i_ret = 0;
	if (sp.x < 0 || sp.y < 0 ||
		sp.x >= m || sp.y >= n) {
		i_ret = 0;
		return i_ret;
	}
	else {
		if (sp.x - 1 >= 0) {  //x-1 
			if (sp.y - 2 >= 0) { //x-1 y-2;
				postion_c pos;
				pos.x = sp.x - 1;
				pos.y = sp.y - 2;
				if (is_pos_not_duplication(pos))
					next_pos[i_ret++] = pos;
			}
			if (sp.y + 2 < n) { //x-1 y+2;
				postion_c pos;
				pos.x = sp.x - 1;
				pos.y = sp.y + 2;
				if (is_pos_not_duplication(pos))
					next_pos[i_ret++] = pos;
			}
		}
		if (sp.x - 2 >= 0) {  //x-2 
			if (sp.y - 1 >= 0) { //x-2 y-1;
				postion_c pos;
				pos.x = sp.x - 2;
				pos.y = sp.y - 1;
				if (is_pos_not_duplication(pos))
					next_pos[i_ret++] = pos;
			}
			if (sp.y + 1 < n) { //x-2 y+1;
				postion_c pos;
				pos.x = sp.x - 2;
				pos.y = sp.y + 1;
				if (is_pos_not_duplication(pos))
					next_pos[i_ret++] = pos;
			}
		}
		if (sp.x + 1 >= 0) {  //x+1 
			if (sp.y - 2 >= 0) { //x-1 y-2;
				postion_c pos;
				pos.x = sp.x + 1;
				pos.y = sp.y - 2;
				if (is_pos_not_duplication(pos))
					next_pos[i_ret++] = pos;
			}
			if (sp.y + 2 < n) { //x-1 y+2;
				postion_c pos;
				pos.x = sp.x + 1;
				pos.y = sp.y + 2;
				if (is_pos_not_duplication(pos))
					next_pos[i_ret++] = pos;
			}
		}
		if (sp.x + 2 >= 0) {  //x+2 
			if (sp.y - 1 >= 0) { //x-2 y-1;
				postion_c pos;
				pos.x = sp.x + 2;
				pos.y = sp.y - 1;
				if (is_pos_not_duplication(pos))
					next_pos[i_ret++] = pos;
			}
			if (sp.y + 1 < n) { //x-2 y+1;
				postion_c pos;
				pos.x = sp.x + 2;
				pos.y = sp.y + 1;
				if (is_pos_not_duplication(pos))
					next_pos[i_ret++] = pos;
			}
		}
	}
	return i_ret;
}

bool is_param_valid(const char* p) {
	bool b_ret = true;
	int len;
	if (p == NULL) {
		return false;
	}
	len = strlen(p);
	if (len > 0) {
		for (int i = 0; i < len; ++i) {
			if ((*(p + i)) > '9' && (*(p + i)) < '0') {
				b_ret = false;
				break;
			}
		}
	}
	else {
		b_ret = false;
	}
	return b_ret;
}

void print_board() {
	for (int i = 0; i < m; ++i) {
		printf("PID %d:", getpid());
		for (int j = 0; j < n; ++j) {
			if (p_board[i][j].step) {
				printf(" %2d ", p_board[i][j].step);
			}
			else {
				printf(" .. ");
			}
		}
		printf("\n");
	}
}

void custom_main() {
	board_element temp;
	temp.depth = cur_depth;
	temp.step = ++cur_step;
	p_board[p_start.x][p_start.y] = temp;
	choice_size = get_pos(p_start);
	if (choice_size > 1) { //more than one choice
		int step_count = 0;
		printf("PID %d: %d moves possible after move #%d\n",
			getpid(), choice_size, cur_step);
		if (is_root == false) { //非根节点，保存和父进程pipe
			//printf("PID %d: current not root node, pipe id = %d\n", getpid(), pipe_child[1]);
			//pipe_parent_write = pipe_child[1];
			//close(pipe_child[0]);
			//close(pipe_child[1]);
			//printf("close pipe sockets\n");
		}
		else { //根节点
			pipe_parent_write = -1;
		}
		if (pipe(pipe_child) == -1) {
			perror("create pipe failed");
			exit(EXIT_FAILURE);
		}
		printf("PID %d:created pipe id [%d:%d]\n",getpid(), pipe_child[0], pipe_child[1]);
		//printf("PID %d:create write pipe id=%d\n", getpid(), pipe_child[1]);

		for (int i = 0; i < choice_size; ++i) {
			pid_t pid = fork();
			if (pid < 0) {
				printf("fork() failed");
				return;
			}
			if (pid == 0) {  //child process
				//printf("PID %d: in child process\n", getpid());
				is_root = false;
				p_prev = p_start;
				p_start = next_pos[i];
				cur_choice_index = i;
				cur_depth++;
				pipe_parent_write = pipe_child[1];
				printf("PID %d:close pipe fd %d:\n",getpid(), pipe_child[0]);
				close(pipe_child[0]);
				printf("PID %d: PPID %d: writepipe%d\n", getpid(), getppid(), pipe_parent_write);
				custom_main();
			}
			else {
				close(pipe_child[1]);
			}
		}
		while (choice_size > 0) {
			
			//printf("PID %d:enter wait choice_size = %d > 0\n", getpid(), choice_size);
			wait(NULL);
			while (read(pipe_child[0], &ch_pipe, 1) > 0) {
				//print out data;
				step_count = ch_pipe - '0';
				printf("PID %d: Received %d from child\n", getpid(), step_count);
				break;
			}
			--choice_size;
		}
		if (is_root) {
			printf("PID %d: Best solution found visits %d squres (out of %d)\n", getpid(), step_count, m*n);
		}	
	}
	else if (choice_size == 1) {//just one choice
		p_start = next_pos[0];
		if (is_root == false) { //非根节点，保存和父进程pipe
			//pipe_parent_write = pipe_child[1];
		}
		custom_main();
	}
	else if (choice_size == 0) { //已经到了叶子节点
		if (is_root == false) { //非根节点
			int total_step = cur_step; //+ cur_depth - 1;
			char ch_num;
			printf("PID %d: Dead end after move #%d\n",
				getpid(), total_step);
			printf("PID %d: Sent %d on pipe to parent\n",
				getpid(), total_step);
			ch_num = '0' + total_step;
			printf("PID %d: write data topipe%d\n", getpid(), pipe_parent_write);
			write(pipe_parent_write, &ch_num, 1);
		}
		else { //root node

		}
#ifdef DISPLAY_BOARD
		print_board();
#endif
	}
}

int main(int argc, char** argv) {

	if (argc != 3) {
		printf("Invalid argument(s)\n");
		printf("USAGE: a.out <m> <n>\n");
		return EXIT_FAILURE;
	}
	if (!is_param_valid(argv[1])) {
		printf("Invalid argument(s)\n");
		printf("USAGE: a.out <m> <n>\n");
		return EXIT_FAILURE;
	}
	if (!is_param_valid(argv[2])) {
		printf("Invalid argument(s)\n");
		printf("USAGE: a.out <m> <n>\n");
		return EXIT_FAILURE;
	}
	m = atoi(argv[1]);
	n = atoi(argv[2]);
	p_start.x = 0;
	p_start.y = 0;
	p_prev.x = 0;
	p_prev.y = 0;
	p_board = NULL;
	alloc_board(m, n);
	is_root = true;
	cur_step = 0;
	cur_depth = 1;
	cur_choice_index = -1;

	if (p_board == NULL) {
		return EXIT_FAILURE;
	}
	//printf("enter custom_main from root\n");
	custom_main();

	return EXIT_SUCCESS;
}
